{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #寻找文件副本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRepeatDocument"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找文件副本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设备中存有 <code>n</code> 个文件，文件 <code>id</code> 记于数组 <code>documents</code>。若文件 <code>id</code> 相同，则定义为该文件存在副本。请返回任一存在副本的文件 <code>id</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>documents = [2, 5, 3, 0, 5, 0]\n",
    "<strong>输出：</strong>0 或 5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 ≤ documents[i] ≤ n-1</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 100000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-zu-zhong-zhong-fu-de-shu-zi-lcof](https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-zu-zhong-zhong-fu-de-shu-zi-lcof](https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2, 5, 3, 0, 5, 0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        for i in range(len(documents)):\n",
    "            x = documents[i]\n",
    "            if x in documents[:i]:\n",
    "                return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        i = 0\n",
    "        while i < len(documents):\n",
    "            if documents[i] == i:\n",
    "                i += 1\n",
    "                continue\n",
    "            if documents[i] == documents[documents[i]]:\n",
    "                return documents[i]\n",
    "            documents[documents[i]], documents[i] = documents[i], documents[documents[i]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        dLen:int = len(documents)\n",
    "        idx:int = 0\n",
    "        while idx < dLen:\n",
    "            if documents[idx] == idx:\n",
    "                idx += 1\n",
    "                continue\n",
    "                \n",
    "            if documents[documents[idx]] == documents[idx]:\n",
    "                return documents[idx]\n",
    "            else:\n",
    "                documents[documents[idx]], documents[idx] = documents[idx],documents[documents[idx]]\n",
    "        return -1\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        documents.sort()\n",
    "        for i in range(len(documents)):\n",
    "            if documents[i] == documents[i - 1]:\n",
    "                return documents[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        i = 0\n",
    "        while i < len(documents):\n",
    "            if documents[i] == i:\n",
    "                i += 1\n",
    "                continue\n",
    "            if documents[documents[i]] == documents[i]: return documents[i]\n",
    "            documents[documents[i]], documents[i] = documents[i], documents[documents[i]]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        i = 0\n",
    "        while i < len(documents):\n",
    "            if documents[i] == i:\n",
    "                i+=1\n",
    "                continue\n",
    "            if documents[i] == documents[documents[i]]:\n",
    "                return documents[i]\n",
    "            documents[documents[i]], documents[i] = documents[i], documents[documents[i]]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        n = len(documents)\n",
    "        for i in range(n):\n",
    "            while i != documents[i]:\n",
    "                if documents[i] == documents[documents[i]]:\n",
    "                    break\n",
    "                documents[documents[i]], documents[i] = documents[i], documents[documents[i]]\n",
    "        for i in range(n):\n",
    "            if documents[i] != i:\n",
    "                return documents[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        temp = 0\n",
    "        for i in range(len(documents)):\n",
    "            while documents[i] != i:\n",
    "                if documents[i]==documents[documents[i]]:\n",
    "                    return documents[i]\n",
    "                temp = documents[i]\n",
    "                documents[i] = documents[temp]\n",
    "                documents[temp] = temp\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        documents.sort()\n",
    "        print(documents) \n",
    "        for i in range(0, len(documents)-1):\n",
    "            if documents[i] == documents[i+1]:\n",
    "                return documents[i]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        documents = sorted(documents)\n",
    "        for i in range(len(documents)-1):\n",
    "            if documents[i]==documents[i+1]:\n",
    "                return documents[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        dic_n = {}\n",
    "        for x in documents:\n",
    "            if x not in dic_n:\n",
    "                dic_n[x] = 0\n",
    "            else:\n",
    "                return x\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        hash = {}\n",
    "        for i in range(len(documents)):\n",
    "            if documents[i] not in hash:\n",
    "                hash[documents[i]] = 1\n",
    "            else:\n",
    "                return documents[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        mp=defaultdict(int)\n",
    "        for i in documents:\n",
    "            if mp[i] is 1:\n",
    "                return i\n",
    "            mp[i]+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(documents)):\n",
    "            if documents[i] in dic:\n",
    "                return documents[i]\n",
    "                break\n",
    "            dic[documents[i]] = i    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        set_doc = set()\n",
    "        for doc in documents:\n",
    "            if doc in set_doc:\n",
    "                return doc\n",
    "            set_doc.add(doc)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        #documents.sort()\n",
    "        # for i in documents:\n",
    "        #     if documents.count(i)>1:\n",
    "        #         return i\n",
    "        s = set()\n",
    "        for i in documents:\n",
    "            if i in s:\n",
    "                return i\n",
    "            else:\n",
    "                s.add(i)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        x={}\n",
    "        for i in documents:\n",
    "            if i in x.keys():\n",
    "                return i\n",
    "            else:\n",
    "                x[i]=1\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        docs = {}\n",
    "        for doc in documents:\n",
    "            if doc not in docs:\n",
    "                docs[doc] = 1\n",
    "            else: \n",
    "                return doc\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        count={}\n",
    "        point=0\n",
    "        for i in range(len(documents)):\n",
    "            if not documents[i] in count:\n",
    "                count[documents[i]]=1\n",
    "            else:\n",
    "                point=i\n",
    "                break\n",
    "        return documents[point]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        if documents is None:\n",
    "            return -1\n",
    "        hmapset = set()\n",
    "        for i in documents:\n",
    "            if i in hmapset:\n",
    "                return i\n",
    "            hmapset.add(i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents):\n",
    "        hmap = set()\n",
    "        for i in documents:\n",
    "            if i in hmap:\n",
    "                return i\n",
    "            else:\n",
    "                hmap.add(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        temp = set()\n",
    "        for item in documents:\n",
    "            if item in temp: return item\n",
    "            temp.add(item)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        dic = set()\n",
    "        for num in documents:\n",
    "            if num in dic: return num\n",
    "            dic.add(num)\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        set1=set()\n",
    "        while documents:\n",
    "            num=documents.pop() \n",
    "            if num in set1:\n",
    "                return num\n",
    "            else:\n",
    "                set1.add(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, nums: List[int]) -> int:\n",
    "        my_set = set(nums)\n",
    "        my_dic = {}\n",
    "        for i in nums:\n",
    "            if my_dic.get(i):\n",
    "                return i\n",
    "            else:\n",
    "                my_dic[i] = True\n",
    "        return None\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        # 对documents中每个元素的出现频率进行计数\n",
    "        temp_list = [[] for _ in documents]\n",
    "        for i in range(len(documents)):\n",
    "            temp_list[documents[i]].append(documents[i])\n",
    "        \n",
    "        # 遍历temp_list，查找出现频率大于1的数\n",
    "        for j in range(len(temp_list)):\n",
    "            if len(temp_list[j]) > 1: return temp_list[j][0]\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        documents.sort()\n",
    "        D = list(set(documents))\n",
    "        length = len(D)\n",
    "        i = 0\n",
    "        while 1:\n",
    "            if documents[i] != D[i]:\n",
    "                return documents[i]\n",
    "            else:\n",
    "                i += 1\n",
    "            if i == length:\n",
    "                return documents[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        res = []\n",
    "        dic = {}\n",
    "        for d in documents:\n",
    "            dic[d] = dic.get(d, 0) + 1\n",
    "            if dic[d] > 1:\n",
    "                res.append(d)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        d = {}\n",
    "        num = -1\n",
    "        for document in documents:\n",
    "            d[document] = -1\n",
    "        for document in documents:\n",
    "            if d[document] == -1:\n",
    "                d[document] += 1\n",
    "            elif d[document] == 0:\n",
    "                num = document\n",
    "                break;\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in documents:\n",
    "            dic[i]=1\n",
    "        for i in documents:\n",
    "            if dic[i]>1:\n",
    "                return i\n",
    "            dic[i] += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        i_count = {}\n",
    "        for i in documents:\n",
    "            if i in i_count:\n",
    "                i_count[i] += 1\n",
    "            else:\n",
    "                i_count[i] = 1\n",
    "        for i in i_count.keys():\n",
    "            if i_count[i] > 1:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRepeatDocument(self, documents: List[int]) -> int:\n",
    "        ids = {}\n",
    "        for document in documents:\n",
    "            ids[document] = ids.get(document, 0) + 1\n",
    "        \n",
    "        for id, freq in ids.items():\n",
    "            if freq > 1:\n",
    "                return id \n",
    "        return None \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
